package com.btashov.linkedlist;

import com.btashov.datastructure.LinkedListNode;
import com.btashov.datastructure.Node;


/**
 * todo: 2.2 Implement an algorithm to find the nth to last element of a singly linked list.
 * <p/>
 * Algorithm:
 * 1. Create two pointers, p1 and p2, that point to the beginning of the node.
 * 2. Increment p2 by n-1 positions, to make it point to the nth node from the beginning (to make the distance of n between p1 and p2).
 * 3. Check for p2->next == null if yes return value of p1, otherwise increment p1 and p2. If next of p2 is null it means p1 points to the nth node from the last as the distance between the two is n.
 * 4. Repeat Step 3.
 */
public class Search {


    public static Node getNthToLast(LinkedListNode listNode, int num) {
        if (listNode.getHead() == null) {
            throw new IllegalArgumentException("list cannot be null");
        }

        Node nodeA = listNode.getHead();
        Node nodeB = listNode.getHead();
        for (int i = 1; i < num; i++) {
            if (nodeB == null) {
                throw new IllegalArgumentException("num can't be more that list size");
            }
            nodeB = nodeB.getNext();
        }

        while (nodeB.getNext() != null) {
            nodeA = nodeA.getNext();
            nodeB = nodeB.getNext();
        }

        return nodeA;
    }

    /**
     * Function to return the nth node from the end of a linked list.
     * Takes the head pointer to the list and n as input
     * <p/>
     * The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
     * so we want p2 to point to the (n-1)th node from the start of the list
     * then we move p2 till it reaches the last node of the list.
     * Once p2 reaches end of the list p1 will be pointing to the nth node
     * from the end of the list.
     * <p/>
     * while moving p2 check if it becomes NULL, that is if it reaches the end
     * of the list. That would mean the list has less than n nodes, so its not
     * possible to find nth from last, so return NULL.
     *
     * @param listNode LinkedListNode
     * @param n        int
     * @return the nth node from the end if one exists else returns NULL.
     */
    public static Node nthToLastFromStackOverflow(LinkedListNode listNode, int n) {

        if (listNode == null || n < 1) {
            return null;
        }

        // make pointers p1 and p2 point to the start of the list.
        Node nodeA = listNode.getHead();
        Node nodeB = listNode.getHead();

        // loop to move p2.
        for (int j = 0; j < n - 1; ++j) {

            if (nodeB == null) {
                return null;
            }
            // move p2 forward.
            nodeB = nodeB.getNext();
        }

        // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
        // till p2 reaches the last node in the list.
        while (nodeB.getNext() != null) {
            nodeA = nodeA.getNext();
            nodeB = nodeB.getNext();
        }

        // at this point p2 has reached the last node in the list and p1 will be
        // pointing to the nth node from the last..so return it.
        return nodeA;
    }
}
